package jianzhi

func exist(board [][]byte, word string) bool {

	if len(board) == 0 || len(board[0]) == 0 {
		return false
	}

	b := []byte(word)

	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if board[i][j] == b[0] {
				if helper12(i, j, board, b) {
					return true
				}
			}
		}
	}

	return false
}

func helper12(i, j int, board [][]byte, word []byte) bool {

	if i < 0 || i > len(board)-1 || j < 0 || j > len(board[0])-1 || board[i][j] != word[0] {
		return false
	}

	if len(word) == 1 {
		return true
	}

	temp := board[i][j]
	board[i][j] = '1'

	if helper12(i-1, j, board, word[1:]) || helper12(i+1, j, board, word[1:]) || helper12(i, j-1, board, word[1:]) || helper12(i, j+1, board, word[1:]) {
		return true
	}

	board[i][j] = temp
	return false
}
